//https://leetcode.cn/problems/count-the-number-of-good-nodes/submissions/589199154/
class Solution {
public:
    int countGoodNodes(vector<vector<int>>& edges) {
        int n = edges.size() + 1;
        vector<int> e[n];
        for (auto& edge : edges) {
            e[edge[0]].push_back(edge[1]);
            e[edge[1]].push_back(edge[0]);
        }

        int ans = 0;
        int f[n];
        auto dfs = [&](auto&& self, int sn, int fa) -> int {
            f[sn] = 1;
            int mn = 1e9, mx = -1e9;
            for (int fn : e[sn]) if (fn != fa) {
                int t = self(self, fn, sn);
                f[sn] += t;
                mn = min(mn, t);
                mx = max(mx, t);
            }
            if (mn >= mx) ans++;
            return f[sn];
            };
        dfs(dfs, 0, -1);
        return ans;
    }
};
